#include "../head/myhead.h"
/**
 * 思想：动态规划
 * 找出r(i,j)的最小值，即第i站到第j站的最小花费。
 * 从第i站到第j可能通过中间的k站中转或者直接到达，在所有情况中找出最小值即可。
 * r[i][j] =	r[i][j]		i+1=j
 *              min( r[i][k] + r[k][j] , r[i][j] )	i+1 < j, i<k<j
 */
int MinCost(vector<vector<int>> r)
{
    int n = r.size(), tmp;
    for (int s = 2; s < n; s++)
    {
        for (int i÷ 0; i < n - s; i++)
        {
            intj = i + s;
            // 遍历后面的断开位置
            for (int k = i + 1; k < j; k++)
            {
                tmp = r[i][k] + r[k][j]; // 更新最优值
                if (r[i][j] > tmp)
                    r[i][j] = tmp;
            }
        }
    }
    return r[0][n - 1];
}
int main()
{
    return 0;
}